1. Field of the Invention
The present invention relates to a method and a system for performing a search on a textual data base. In particular, the present invention relates to searching a textual data base and presenting the search results to a query as it is typed.
2. Discussion of the Related Art
In many systems for searching public or personal data today (e.g., Google Suggest or Facebook Search), the user interface “suggests” a completion to a user query as the user types the query into a text box. In such systems, the suggestion is provided in the form of a list of possible queries that the user can select in lieu of typing out the remainder of the query. When the query is selected or completely typed out, the query is submitted to the search server which then returns the results of the search. In conventional systems (e.g., distributed systems such as BigTable, Cassandra and Sphinx), the search is performed on data which resides either in memory or on-disk. However, to date, there is no known system which performs a search in real time using the portion of the query already typed, and returns the actual search results responsive to that portion of the query. This is because such a capability is technically challenging, as it requires very fast searches on textual data. To implement such fast searches, it is preferred to avoid time-consuming disk accesses; however, such an approach would require keeping the data to be searched in memory, which is a very limited resource.